package com.example.arithmeticleetcode.learnArithmetic2.recursion;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-12-04 11:52
 **/
public class Hanoi {

    public static void main(String[] args) {
        hanoi(3, "A", "B", "C");
    }

    /**
     * 将n个盘子从p1移动到p2
     *
     * @param n
     * @param p1
     * @param p2 中间的篮子
     * @param p3 时间复杂度 T(n) = 2* T(n - 1) + O(1) -> 2^n 空间复杂度O(n)
     */
    static void hanoi(int n, String p1, String p2, String p3) {
        //一般看递归条件
        if (n == 1) {
            move(n, p1, p3);
            return;
        }
        hanoi(n - 1, p1, p3, p2);
        move(n, p1, p3);
        hanoi(n - 1, p2, p1, p3);
    }

    static void move(int no, String from, String to) {
        System.out.println("将" + no + "号盘子从" + from + "移动到" + to);
    }

}
